• This assignment is optional.
• You will not need to join the Ohyay workspace today.
• This assignment will be an individual submission.
• You will submit your Revised Flowchart PDF and Solution PDF to GradeScope for this assignment.

Read

Hello students.

I am digging a big pit of rooms to throw Dr. Bart into.

I have a set of N room designs, each with dimensions L_i, W_i, H_i. I want to stack the rooms vertically so that the rooms go as deep into the ground as possible. However, I can only place a room above a second room if the first room has a strictly smaller area. In other words, the bases of the rooms must get smaller as we go further down. Note that the base of a room j is Lj*Wj. I can rotate the designs so that any side functions as its base. I can also reuse multiple instances of the same design.

Give an efficient algorithm to construct the deepest stack of rooms, where the depth is the sum of the heights of each room in the stack.

Do

This assignment is extra credit. You do not have to help AlgoTutorBot dig a pit to throw Dr. Bart into.

You will be revising your flowchart again. Then, you will solve the algorithmic problem above.

Revise your flowchart

Return to the Algorithmic Flowchart that you created previously (in Lessons 8, 12, and 17). Update and improve on your Flowchart to incorporate what you have learned about Dynamic Programming. This flowchart is a reflection of what you have learned about solving algorithmic problems. Demonstrate to us that you have more strategies than you did before!

Submission

Upload the following to GradeScope: https://www.gradescope.com/courses/230699/assignments/1191741/

1. The latest version of your Algorithmic Flowchart
2. Everything you wrote down while solving the problem (including reflections)

All files should be in PDF format.